n=100;
roads=[|1,2|
1,3|
4,1|
4,5|
6,4|
4,7|
8,7|
9,7|
7,10|
10,11|
10,12|
13,5|
14,13|
15,13|
13,16|
13,17|
18,13|
13,19|
19,20|
21,19|
22,19|
11,23|
19,24|
25,19|
26,19|
19,27|
28,19|
29,19|
19,30|
19,31|
13,32|
19,33|
34,19|
19,35|
36,19|
36,37|
36,38|
36,39|
39,40|
41,40|
42,41|
41,43|
44,43|
43,45|
43,46|
47,43|
48,27|
49,48|
49,50|
51,49|
49,52|
49,53|
54,49|
49,55|
56,49|
57,49|
58,57|
37,59|
60,59|
61,59|
62,59|
59,63|
64,63|
65,63|
63,66|
63,67|
68,63|
63,69|
70,63|
63,71|
63,72|
72,73|
72,74|
6,75|
76,72|
77,8|
78,72|
78,79|
78,80|
81,80|
80,82|
82,83|
84,83|
85,83|
85,86|
87,85|
85,88|
75,89|
85,90|
85,91|
92,85|
85,93|
85,94|
95,85|
15,96|
97,85|
85,98|
99,85|
100,85|];
W=[10,41,62,19,9,99,17,84,77,94,33,70,22,75,43,13,80,38,22,6,75,59,74,76,39,30,62,98,78,12,15,81,85,23,28,98,47,2,85,59,51,17,1,51,16,11,82,51,67,52,12,77,69,2,27,70,55,50,48,18,52,8,8,48,46,87,26,47,59,72,16,62,22,63,65,61,44,83,66,40,74,32,32,25,46,39,20,85,65,91,62,68,75,32,10,63,88,47,49,36];